package com.archway.appframe.frame.utils.alg;

import java.util.Comparator;
import java.util.List;

/**
 * 二分查找及相关内容扩展
 * 
 * @author lirn-desk
 * 
 */
public class Bisection {

	
	
	
	
	/**
	 * 模糊的二分匹配，使用场景有限
	 * @param srcList
	 * @param des
	 * @param cmp
	 * @return
	 */
	public static  int[] blurSearch(List<?> srcList, Object des, Comparator<Object> cmp) {
		int[] rtn = null;
		int[] lastComp = new int[2]; //如果最后一次比较
		int _cmp;
		int low = 0;
		int high = srcList.size() - 1;
		while (low <= high) {
			int middle = (low + high) / 2;
			_cmp = cmp.compare(des, srcList.get(middle));
			if (_cmp == 0) {
				rtn = new int[1];
				rtn[0]=middle;
				return rtn;
			} else if (_cmp < 0) {
				high = middle - 1;
				lastComp[0]=low;
				lastComp[1]=middle;

			} else {
				lastComp[0]=middle;
				lastComp[1]=high;
				low = middle + 1;
			}
		}
		if(low>high){
			rtn=lastComp;
		}

		return rtn;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	// ====忽略如下标准实现===========================================
	/**
	 * * 二分查找算法 * *
	 * 
	 * @param srcArray
	 *            有序数组 *
	 * @param des
	 *            查找元素 *
	 * @return des的数组下标，没找到返回-1
	 */
	@Deprecated
	public static int search(int[] srcArray, int des) {

		int low = 0;
		int high = srcArray.length - 1;
		while (low <= high) {
			int middle = (low + high) / 2;
			if (des == srcArray[middle]) {
				return middle;
			} else if (des < srcArray[middle]) {
				high = middle - 1;
			} else {
				low = middle + 1;
			}
		}
		return -1;
	}

	/**
	 * 二分查找特定整数在整型数组中的位置(递归)
	 *  递归在互联网中基本不建议使用
	 * @paramdataset
	 * @paramdata
	 * @parambeginIndex
	 * @paramendIndex
	 * @returnindex
	 */
	@Deprecated
	public static int search(int[] dataset, int data, int beginIndex,
			int endIndex) {
		int midIndex = (beginIndex + endIndex) / 2;
		if (data < dataset[beginIndex] || data > dataset[endIndex]
				|| beginIndex > endIndex) {
			return -1;
		}
		if (data < dataset[midIndex]) {
			return search(dataset, data, beginIndex, midIndex - 1);
		} else if (data > dataset[midIndex]) {
			return search(dataset, data, midIndex + 1, endIndex);
		} else {
			return midIndex;
		}
	}

}
